/************************************************************************************************
 * test examples of 100 interesting program in C
 * test 061.c
 * 1~9 to compose 3 3-digit numbers which are squared numbers
 * not original solution, but using table to accelerate selection
 ***********************************************************************************************/

#include <stdio.h>
#include <string.h>

/*
 * it is strange to see that:
 * int** cannot be using in processing 2D integer array a[][]
 *
 * and this solution is somehow dirty, no better than exhausting
 */

#define LINES 10
#define ROWS 20

int table[ROWS][LINES];
int table_x[ROWS][LINES];

int printTable()
{
	int i = 0, j = 0;
	for (i = 0; i < ROWS; i++)
	{
		printf("%8d", table[i][0]);
		for (j = 1; j < LINES; j++)
			printf("%4d", table[i][j]);
		printf("\n");
	}
}

int deleteZ(int r)
{
	while (table_x[r][0] < 0) r++;

	int n = table_x[r][0];
	int i = 0;
	for (i = 1; i < LINES; i++)
	{
		if (table_x[r][i] == 0) continue;
		// for each line, find numbers has same digit
		int j = 0;
		for (j = r+1; j < ROWS; j++)
		{
			if (table_x[j][0] == 0) break;
			if (table_x[j][0] < 0) continue;
			if (table_x[j][i] == 1) table_x[j][0] = 0 - table_x[j][0];
		}
	}
}

// print result start from the i(th) row
int printResult(int i)
{
	int a = 0, b = 0, c = 0;

	while (table_x[i][0] < 0) i++;

	if (table_x[i][0] == 0) return(0);
	else a = table_x[i++][0];

	while (table_x[i][0] < 0) i++;

	if (table_x[i][0] == 0) return(0);
	else b = table_x[i++][0];

	for (; i < ROWS; i++)
	{
		if (table_x[i][0] == 0) return(0);
		if (table_x[i][0] < 0) continue;
		printf("<%d, %d, %d> is found in composition of 1~9.\n", a, b, table_x[i][0]);
	}

	return(1);
}

int delete()
{
	int i = 0;
	int flag = 0;

	for (i = 0; i < ROWS; i++)
	{
		if (table[i+2][0] == 0) break; // number remain is not enough (<3)

		memcpy(table_x, table, sizeof(int)*ROWS*LINES);

		// find group composed with <table[i][0], x, y>,
		// so delete all digit related number of table[i][0] in followed table.
		deleteZ(i);
		deleteZ(i+1);

		printResult(i);
	}
}

int main()
{
	memset(table, 0, sizeof(int)*ROWS*LINES);

	int i = 0, n = 0, curr_row = 0;
	for (i = 10, n = i*i; n < 1000; ++i, n = i*i)
	{
		int a = n/100, b = (n%100)/10, c = n%10;
		if ((a != b) && (b != c) && (a != c))
		{
			table[curr_row][0] = n;
			table[curr_row][a] = 1;
			table[curr_row][b] = 1;
			table[curr_row][c] = 1;
			curr_row++;
		};
	}

	printTable();

	delete();
}

